/* qap-example - Solve a QAP problem using SA, GA, and Hill Climbing
 *
 * Copyright (c) 2007 Christopher Alexander Watford
 * <christopher.watford@gmail.com>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to
 * deal in the Software without restriction, including without limitation the
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 * sell copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
 * IN THE SOFTWARE.
 *
 * $Id$
 */

#include <cstdlib>
#include <iostream>

#include <opt.hpp>
#include <sa.hpp>
#include <ga.hpp>
#include <hillclimber.hpp>
#include <utils.hpp>

class QAPProblem : public IFitnessImplementation
{
public:
   QAPProblem(size_t n, double *costFlowMat)
      : _m_Facilities(n), _m_Locations(n)
      , _m_Cost(costFlowMat), _m_Assignment((n+1)*n)
      , _m_Fitness(std::numeric_limits<double>::quiet_NaN())
   {
      watopt::seed_random();
   }

   QAPProblem(const QAPProblem& other)
   {
      this->_m_Facilities = other._m_Facilities;
      this->_m_Locations = other._m_Locations;
      this->_m_Cost = other._m_Cost;
      this->_m_Fitness = other._m_Fitness;

      this->_m_Assignment = new bool[_m_Facilities*_m_Locations];
      std::memcpy(this->_m_Assignment, other._m_Assignment, sizeof(bool)*_m_Facilities*_m_Locations);
   }

   QAPProblem&
   operator= (const QAPProblem& other)
   {
      if(this != &other)
      {
         this->_m_Facilities = other._m_Facilities;
         this->_m_Locations = other._m_Locations;
         this->_m_Cost = other._m_Cost;
         this->_m_Fitness = other._m_Fitness;

         this->_m_Assignment = new bool[_m_Facilities*_m_Locations];
         std::memcpy(this->_m_Assignment, other._m_Assignment, sizeof(bool)*_m_Facilities*_m_Locations);
      }

      return *this;
   }

   double
   Fitness(void)
   {
      if(_m_Fitness != std::numeric_limits<double>::quiet_NaN())
         return _m_Fitness;

      // does not penalize solutions with multiple edges
      _m_Fitness = 0.0;
      for(size_t ii = 0; ii < _m_Locations; ii++)
      {
         for(size_t jj = 0; jj < _m_Facilities; jj++)
         {
            if(_m_Assignment[ii*_m_Facilities + jj])
            {
               double flow = _m_Cost[jj*_m_Locations + ii];
               double dist = _m_Cost[ii*_m_Facilities + jj];

               _m_Fitness += dist*flow;
            }
         }
      }

      return _m_Fitness;
   }

   IFitnessImplementation* Perturb(void)
   {
      _m_Fitness = std::numeric_limits<double>::quiet_NaN();

      QAPProblem *altered = new QAPProblem(*this);

      // pick two rows, swap them
      size_t r1 = watopt::rand_index(_m_Locations);
      size_t r2 = r1;
      while((r2 = watopt::rand_index(_m_Locations)) == r1);

      // use the extra row we allocated to save temp data
      bool *temp = &altered->_m_Assignment[_m_Locations*_m_Facilities];
      std::memcpy(temp, &altered->_m_Assignment[r1*_m_Facilities], sizeof(bool)*_m_Facilities);
      std::memcpy(&altered->_m_Assignment[r1*_m_Facilities], &altered->_m_Assignment[r2*_m_Facilities],
         sizeof(bool)*_m_Facilities);
      std::memcpy(&altered->_m_Assignment[r2*_m_Facilities], temp, sizeof(bool)*_m_Facilities);

      return altered;
   }

   IFitnessImplementation* LocalOpt(void)
   {
      return NULL;

      /*_m_Fitness = std::numeric_limits<double>::quiet_NaN();

      QAPProblem *altered = new QAPProblem(*this);

      return altered;*/
   }

   void Neighbors(std::vector<IFitnessImplementation*>& neighbors) 
   {
      // need to think about this one
      neighbors.push_back(Perturb());
   }

private:
   size_t _m_Facilities;
   size_t _m_Locations;
   bool *_m_Assignment;
   double *_m_Cost;
   double _m_Fitness;
};